package linkedlist;

/**
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。
 * 如果是，返回 true ；
 * 否则，返回 false 。
 */
public class no234 {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null){
            return true;
        }
        ListNode cur = head;
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode newHead = slow.next;
        ListNode temp = null;
        ListNode prev = newHead;
        while (newHead != null){
            prev = prev.next;
            newHead.next = temp;
            temp = newHead;
            newHead = prev;
        }
        while (temp != null){
            if (temp.val != cur.val){
                return false;
            }
            temp = temp.next;
            cur = cur.next;
        }
        return true;
    }
}
